package net.zjitc.tree;

public class BTree {
    TreeNode<Integer> root;
    //二叉排序树： 唯一
    //中序：有序
    //效率高
    public void add(Integer value){
        //根节点
       if (root == null){
           root = new TreeNode<>(value);
           return;
       }
       //插入？先比较（每次都是从根进行比较），再插入（一定是没有孩子才能插入）

        //每次都是从根进行比较
        TreeNode<Integer> currentNode = root;
        //比较
       while (true){
           if (value<currentNode.data){//向左走
               if (currentNode.Left == null){//插入
                   currentNode.Left = new TreeNode<>(value);
                   return;
               }
               currentNode = currentNode.Left;
           }else if (value > currentNode.data){
               if (currentNode.right == null){
                   currentNode.right = new TreeNode<>(value);
                   return;
               }
               currentNode = currentNode.Left;
           }else {
               return;
           }
       }
    }

    /**
     * 树中是否存储此值
     * @param key
     * @return
     */
    public boolean serach(int key){

        TreeNode<Integer> currentNode = root;
        while (true){
            if (currentNode == null){
                return false;
            }
            if (currentNode.data == key){
                return true;
            }
            if ( key < currentNode.data ){
                currentNode = currentNode.Left;
            }else {
                if (key > currentNode.data ){
                    currentNode = currentNode.right;
                }
            }
        }
    }

    /**
     * 另一种方法找（递归）
     * @param node
     */

    public boolean find(TreeNode<Integer> node,int key){
        if (node == null){
            return false;
        }
        if (key == node.data){
            return true;
        }
        if (key > node.data){
           return find(node.right,key);
        }else{
            return find(node.Left,key);
        }
    }

    //中
    public void midOrder(TreeNode node){
        if (node!= null){

            //左
            midOrder(node.Left);
            //根
            System.out.println(node.data);
            //右
            midOrder(node.right);
        }
    }

}
